home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 13308 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.6 KB  |  52 lines

  1. Newsgroups: comp.lang.c,comp.lang.perl
  2. Path: netcom.com!crewman
  3. From: crewman@netcom.com (Kevin L. Weller)
  4. Subject: Re: Random File Access - I don't get it
  5. Message-ID: <crewmanDpEEAy.LI6@netcom.com>
  6. Sender: crewman@netcom2.netcom.com
  7. Organization: Me, Myself, and I
  8. X-Newsreader: Forte Free Agent 1.0.82
  9. References: <3160DE1E.495C@teleport.com>
  10. Date: Fri, 5 Apr 1996 16:41:46 GMT
  11.  
  12. Scott Kinard <kinards@teleport.com> wrote:
  13. >  Suppose I have two files, one contains text (1 line of random length text per 
  14. >'record') and another which is my index into the text file, which contains the starting 
  15. >and ending byte positions in the text file for each 'record'. Now the question..
  16. >Suppose the text file has 2,000,000 entries. Now, what's the difference in reading 
  17. >1,000,000 lines from the index file to find the starting and ending byte positions in 
  18. >the text file for record 1,000,000, and then seeking these in the text file, rather than 
  19. >just reading 1,000,000 times from the text file to get the same 'record' in the first 
  20. >place?
  21.  
  22. There may not be much advantage if the index is not sorted, unless the
  23. index records are very small.  Chances are, though, if there is an
  24. index, it IS sorted.  Depending on HOW it's sorted, you can either:
  25.  
  26. 1) Use a divide-and-conquer approach (a binary search) on the index to
  27. find the index record (average time complexity base 2 log n), then
  28. perform one read from the text file (so on average, your
  29. 2,000,000-record example would take about base 2 log 2,000,000 + 1, or
  30. approximately 22 reads, a h*ll of a lot better than 1,000,000!).
  31. Somebody please correct my math if it's off.... :-)
  32.  
  33. 2) If the index is organized by a hashing function, the whole process
  34. should take only two reads (assuming no key collisions): one to hash
  35. into the index, and the other to read the text file.
  36.  
  37. Either case is tremendously better than the average n/2 reads
  38. (2,000,000 / 2 = 1,000,000 in this case) a sequential search of the
  39. text file would require.
  40.  
  41. Be cool!
  42.  
  43. ------------------------------------------------------------------------------
  44. Kevin L. Weller, a.k.a. Crewman!!!              /-------+--------------------\
  45. crewman@netcom.com                              |  aTm  |  GIG 'EM, AGGIES!  |
  46. This is my personal (non-business) account      \-------+--------------------/
  47. ------------------------------------------------------------------------------
  48. %SYS-E-BADOPSYS, Fatal system error, DEC VMS halting \ All wiyht. Rho sritched
  49. -SYS-I-GETUNIX, Replace with UNIX immediately!        \     mg kegtops awound?
  50. ------------------------------------------------------------------------------
  51.  
  52.